#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <cstring>
using namespace std;
class Solution 
{
public:
	string minWindow(string S, string T)
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		if(T.empty() || S.size()<T.size())
			return "";
		int hist1[256], hist2[256];
		memset(hist1,0,sizeof(hist1));
		memset(hist2,0,sizeof(hist2));

		for(size_t i=0;i<T.size();i++)
		{
			hist2[T[i]]++;
		}

		size_t tFound = 0;
		size_t head = 0, tail = 0;
		size_t minLen = -1,minHead = head;


		while(tail<S.size())
		{
			while(tFound<T.size() && tail<S.size())
			{
				if(hist2[S[tail]]>0)
				{
					hist1[S[tail]]++;
					if(hist1[S[tail]]<=hist2[S[tail]])
						tFound++;
				}
				tail++;
			}

			//not found
			if(tFound<T.size())
			{
				break;
			}

			while(head<tail)
			{
				if(hist2[S[head]]>0)
				{
					hist1[S[head]]--;
					if(hist1[S[head]]<hist2[S[head]])
					{
						tFound--;
						break;
					}
				}
				head++;
			}

			size_t curLen = tail-head;
			if(curLen<minLen)
			{
				minHead = head;
				minLen = curLen;
			}
			head++;
		}

		if(minLen==-1)
			return "";
		else
			return S.substr(minHead,minLen);
	}
};
#endif
